#include <bits/stdc++.h>
#ifndef DEBUG
#define debug
#endif
using namespace std;
using i64 = int64_t;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int c, n, m, q;
  cin >> c >> n >> m >> q;
  vector<int> X(n + 1), Y(m + 1);
  for (int i = 1; i <= n; i ++) cin >> X[i];
  for (int i = 1; i <= m; i ++) cin >> Y[i];

  auto x = X, y = Y;

  auto solve = [&]() {
    if (x[1] == y[1] || x[n] == y[m]) return '0';
    if ((x[1] < y[1]) != (x[n] < y[m])) return '0';
    if (x[1] > y[1]) x.swap(y);
    // debug(x);
    // debug(y);
    int n = x.size() - 1, m = y.size() - 1;
    
    auto check = [&]() {
      vector<int> pi(n + 1), pj(m + 1), pmax(n + 1), pmin(m + 1);
      pi[1] = 1, pmax[1] = x[1];
      for (int i = 2; i <= n; i ++) {
        pi[i] = x[i] < x[ pi[i - 1] ] ? i : pi[i - 1];
        pmax[i] = max(pmax[i - 1], x[i]);
      }
      pj[1] = 1, pmin[1] = y[1];
      for (int j = 2; j <= m; j ++) {
        pj[j] = y[j] > y[ pj[j - 1] ] ? j : pj[j - 1];
        pmin[j] = min(pmin[j - 1], y[j]);
      }
      int i = pi[n], j = pj[m];
      if (pmax[n] >= y[j] || pmin[m] <= x[i]) return false;
      while (i != 1 && j != 1) {
        if (pmax[i - 1] < y[ pj[j - 1] ]) {
          j = pj[j - 1];
          continue;
        }
        if (pmin[j - 1] > x[ pi[i - 1] ]) {
          i = pi[i - 1];
          continue;
        }
        return false;
      }
      return true;
    };

    if (!check()) return '0';
    reverse(x.begin() + 1, x.end());
    reverse(y.begin() + 1, y.end());
    return check() ? '1' : '0';
  };

  cout << solve();
  while (q --) {
    int k1, k2, id, v;
    cin >> k1 >> k2;
    x = X, y = Y;
    while (k1 --) cin >> id >> v, x[id] = v;
    while (k2 --) cin >> id >> v, y[id] = v;
    cout << solve();
  }
  cout << endl;
}